package seqlist.LeetCode;
//剑指 Offer 22. 链表中倒数第k个节点
/**
 * 输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。
 * 例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。
 */

/**
 * 思路一：总长度 - K。所谓的倒数第k个节点，就是正的数 n - k个节点。所以先统计出总长度
 * 再从头走 n - k次，就是倒数第k个的节点.就是从 head 走 n - k 步的节点
 * 这里还需要考虑k的合法性
 */

/*

public class 剑指offer_Num22_getKthFromEnd {
    public ListNode getKthFromEnd(ListNode head, int k) {

           //边界
        if(head == null || k < 0){
            return null;
        }

        int n = 0;
        //统计链表长度
        for (ListNode x = head; x != null ; x = x.next) {
                n++;
        }
        //如果 n - k小于 0就直接不进入循环
        for (int i = 0; i < n - k; i++) {
            head = head.next;
        }
        return head;
    }
}

 */

/**
 * 思路二：相对距离法。 引入两个引用，slow和 fast。
 * 先让 fast 走 k 步，然后两个引用再同时开始依次向后移动
 * 因为他们相距的距离是不变的，当 fast走到 null头的时候，
 * 此时的 slow正好落在 倒数第 k 个节点的位置上。
 * 不懂的可以逆着想，如果我们让一个指针落在 k 上，一个指针落在 null末尾
 * 它们同时向 左走，当那个落在 k上的指针到头节点的时候停止。一个道理。
 */
//注释：任需要考虑边界问题，k的合法性。
public class 剑指offer_Num22_getKthFromEnd {
    public ListNode getKthFromEnd(ListNode head, int k) {

        //边界
        if(head == null || k < 0){
            return null;
        }

        ListNode slow = head;
        ListNode fast = head;

        for (int i = 0; i < k; i++) {

            if(fast == null){
                //k的合理性 如果还没移动完就走到头了，k肯定是超标了
                return head;
            }
            fast = fast.next;
        }

        while(fast != null){
            slow = slow.next;
            fast = fast.next;
        }

        return  slow;
    }
}